package features.advance.leetcode.dynamicProgramming.easy;

import java.util.Arrays;

/**
 * @author LIN
 * @date 2023-10-18 10:25
 *
 *  338. 比特位计数
 * 简单
 * 给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。
 *
 *
 * 示例 1：
 *
 * 输入：n = 2
 * 输出：[0,1,1]
 * 解释：
 * 0 --> 0
 * 1 --> 1
 * 2 --> 10
 * 示例 2：
 *
 * 输入：n = 5
 * 输出：[0,1,1,2,1,2]
 * 解释：
 * 0 --> 0
 * 1 --> 1
 * 2 --> 10
 * 3 --> 11
 * 4 --> 100
 * 5 --> 101
 *
 *
 * 提示：
 *
 * 0 <= n <= 105
 *
 *
 * 进阶：
 *
 * 很容易就能实现时间复杂度为 O(n log n) 的解决方案，你可以在线性时间复杂度 O(n) 内用一趟扫描解决此问题吗？
 * 你能不使用任何内置函数解决此问题吗？（如，C++ 中的 __builtin_popcount ）
 */
public class Solution338 {

    public static void main(String[] args) {
        Solution solution = new Solution() {
            /***
             * Brian Kernighan 算法
             * 利用 Brian Kernighan 算法，
             * 可以在一定程度上进一步提升计算速度。Brian Kernighan算法的原理是：对于任意整数 xxx，令 x=x&(x−1)，
             * 该运算将 x 的二进制表示的最后一个 1 变成 0。因此，对 x 重复该操作，直到 x 变成 0，则操作次数即为 x 的「一比特数」。
             * @param n
             * @return
             */
            @Override
            public int[] countBits(int n) {
                int[] res = new int[n+1];
                for (int i = 0; i <= n; i++) {
                    res[i] = bkAlgo(i);
                }
                return res;
            }
            int bkAlgo(int x){
                int one = 0;
                while(x>0){
                    x&=(x-1);
                    one++;
                }
                return one;
            }
        };
        int n = 8;
        int[] bits = solution.countBits(n);
        System.out.println(Arrays.toString(bits));

        solution = new Solution() {
        };
        bits = solution.countBits(n);
        System.out.println(Arrays.toString(bits));






    }

    static class Solution {
        public int[] countBits(int n) {
            int[] res = new int[n + 1];
            for (int i = 0; i <= n; i++) {
                String x = Integer.toBinaryString(i);
                System.out.println(x);
                int r = 0;
                for (char c : x.toCharArray()) {
                    r+=c-48;
                }
                res[i] = r;
            }
            return res;
        }
    }
}
